
public class AvoidRoads {
	
	public static void main(String[] args){
		String[] bad = {};

		System.out.println(numWays(35
				,31,bad));
	}
	
	public static long numWays(int width, int height, String[] bad){
		long[][] ways = new long[width+1][height+1];
		ways[0][0]=1;
		for(int i=0;i<width+1;i++){
			for(int j=0;j<height+1;j++){
				if(i>0){
					if(!isBad(i,j,i-1,j,bad))
						ways[i][j]+=ways[i-1][j];
				}
				if(j>0){
					if(!isBad(i,j,i,j-1,bad))
						ways[i][j]+=ways[i][j-1];
				}
			}
		}
		for(int i=0;i<width+1;i++){
			for(int j=0;j<height+1;j++){
				System.out.print(ways[i][j]+" ");
			}
			System.out.println();
		}
		
		return ways[width][height];
	}
	
	public static boolean isBad(int locationI, int locationJ, int i, int j, String[] bad){
		for(int k=0;k<bad.length;k++){
			String badStreet = bad[k];
			if(badStreetEqual(badStreet, locationI,  locationJ,  i,  j)){
				return true;
			}
		}
		return false;
	}

	private static boolean badStreetEqual(String badStreet, int locationI,
			int locationJ, int i, int j) {
		String[] location = badStreet.split("\\s");
		if (location[0].equals(String.valueOf(locationI)) && location[1].equals(String.valueOf(locationJ)) && location[2].equals(String.valueOf(i))&& location[3].equals(String.valueOf(j)))
			return true;
		else if (location[2].equals(String.valueOf(locationI)) && location[3].equals(String.valueOf(locationJ)) && location[0].equals(String.valueOf(i))&& location[1].equals(String.valueOf(j)))
			return true;
		else
			return false;
	}
}
